// 假设一个固定窗口，大小为W，依次划过数组arr，返回每一次滑动后的窗口的最大值
// 例如 arr=[4,3,5,4,3,3,6,7],W=3
// 返回 [5,5,5,4,6,7]
#include"../util/util.h"
#include <deque>
#include <vector>
#include <string>
#include <iostream>
std::vector<int> getMaxWindow(const int *arr, int arrlength, int w)
{
    // 存放返回的结果
    std::vector<int> res;
    if (arr == nullptr || w < 1 || w > arrlength)
    {
        exit(EXIT_FAILURE);
    }
    // 双端队列deque,存放数组元素的下标
    // 且设定它的头部到尾部元素，所对应的arr内数组元素大小是从大到小的
    std::deque<int> qmax;
    for (int R = 0; R < arrlength; R++)
    {
        // 弹出所有比新加入的值小或等于的数
        while (!qmax.empty() && arr[qmax.back()] <= arr[R])
        {
            qmax.pop_back();
        }
        // 将新的值插入到队列尾部
        qmax.push_back(R);
        // 从队列中弹出因窗口变化而被移出的值，因为窗口大小固定，所以R-w为这个值的下标
        if (qmax.front() == R - w)
        {
            qmax.pop_front();
        }
        // 将窗口变化后，窗口内的最大值加入到res中
        // 队头的元素对应arr数组内元素的值是窗口内最大的
        // 当元素的值大于等于窗口的大小w时，才开始记录窗口内最大值
        if (R >= w - 1)
        {
            res.push_back(arr[qmax.front()]);
        }
    }
    return res;
}
int main()
{
    // 数组arr
    int arr[1024] = {0};
    int arrLength = 0;
    arrLength = Util::GetInstance().getArrFromStdin(arr);
    auto vec = getMaxWindow(arr, arrLength, 3);
    for(auto v:vec){
        std::cout<<v<<" ";
    }
    std::cout<<std::endl;
    return 0;
}